Lambda the Ultimate

"... go back to the starting point of procedural programming languages and extend them into a different direction in order to create advanced procedural languages which are significantly simpler than aspect-oriented languages while offering comparable expressiveness and flexibility."

APPLE: Advanced Procedural Programming Language Elements pdf

... Java also acted as a brake especially to academic language design research... The goal of this second edition of the workshop was to address object-oriented languages that diverge from Java’s doctrine but support a much more dynamic way of constructing software. In the near future, this dynamicity will be required in order to construct software that is highly context-dependent due to the mobility of both the software itself and its users...

ECOOP 2004 Workshop - Back to Dynamicity

ECOOP 2003 Workshop

I do system programming. By this, I mean that I use quite a bit of various Posix/Unix APIs and (incidently) lots of TCP/UDP networking stuff on a daily basis to build long running apps that must be very, very solid, scalable and robust. I don't hear a lot about doing this type of programming using FPs and HOPLs. Actually, I don't think that I've heard of much serious system programming work outside of Erlang and (ocassionaly) O'Caml.

I've been using Standard ML (w/ Concurrent ML) these days and have fell in love (or at least a well regarded like) with The Standard ML Basis Library.

Alas, Standard ML doesn't seem to have generated much interest outside of academia. This is a shame, since the Basis covers a lot of practical system stuff.

What are the other higher order languages well suited for system programming? (And, no fair if you have to drop down to C/C++ for Posix, binary data manipulation or networking stuff.)

I am going to initiate a marginally on-topic discussion, Ehud - please correct me if it is not on-topic at all.

Let's say I have a well-defined binary file format¹, consisting of structural elements of different granularity ranging from unsigned ints to tagged blocks to sequences to complete files, and I want to express this structural elements in my PL, covering at least reading the file, analyzing/transforming it at the level of structural elements (as opposed to bits/bytes), and writing it back. An example would be optimizing Flash file for size, while preserving its functionality.

Additional points for:

1. Compile-time checking to some extent (yes, it's unfair)
2. Natural support of tagged blocks - e.g., block with tag 22 must have this type, while block with tag 42 must have that type (explicit "switch" does not count)
3. Natural support of bit-fields (explicit bit-shifting does not count)
4. Ditto with variable bit-field length (Byte n; BitField[n] x; BitField[x] y)
5. Symmetric serialization/deserialization specification (ideally this should be completely defined by the structure of type)

Well, I realize that this sound too much like a DSL for describing file formats, but the question is - which of general-purpose PLs come sufficiently close to this (very informal) specification? Is dependent typing the most natural solution for variable length of fields and tagged blocks?

---

¹If you are familiar with SWF you may think of this hypothetical format as SWF (if not, think RIFF, MIDI, etc.).

Learning to Program with Alice

The goal of our innovative approach is to allow traditional programming concepts to be more easily taught and more readily understood.

I have spent the last year learning Common Lisp and then Scheme. Especially after watching most of the SICP videos, I am completely enamored with Scheme. It was a godsend for my natural language course last semester in which I needed my only constraint to be my imagination rather than my programming language. I am addicted. But I am also in crisis, because Scheme feels both a blessing and a curse. It's a blessing for the obvious reasons, but it's a curse because it doesn't feel like Scheme is everything I want it to be and I don't exactly know why. It feels impractical. I have some (questions about / comments on) on my experience.

First, my Scheme code feels sloppy, much more so than the mind-numbing Java I write for my research job. Is it just all of Java's boilerplateism that's giving it the illusion of better organization? Sure there's more code, but I never have to think twice about where to put that code. Maybe it's Java's rigid design that's forcing me to be more organized when I use it. In imperative languages, the creation of new procedures often feels very arbitrary. It took experience for me to learn when to excise a handful of imperative operations and move them to their own procedure. In Scheme this feels more natural... every procedure seems to map well to the conceptual operation it performs. I think this has a lot to do with functional programming's emphasis on the "computation as calculation" perspective. Because imperative languages highlight the computer's role as a storage device for program state, perhaps they don't lend well to the conceptual breakdown of code into procedures. But is there something about the view of computation as "manipulation of storage" that lends to a better conceptual breakdown when it comes to collections of related procedures? In my Java programs I always feel like there's a place for everything and everything is in its place. My Scheme programs (though I haven't written THAT many full blown programs) always end up being huge listings of procedures grouped into a single massive file... This probably has as much to do with inexperience as it does with language properties, but it also seems true that in Java I have to think about this sort of thing less. What are good organization techniques? Does anyone have advice / guidelines on breaking Scheme programs into compilation units?

Coming from the static world of C++ and Java, one of the most seductive parts of Lisp early-on was its complete type dynamism. Having the straitjacket removed felt wonderful, but as I gain more experience, I'm starting to miss the straitjacket. I know that Haskell and Ocaml are statically typed, and I've ventured a little into Haskell, but I still really like Lisp. It feels more "low-level". I like being able to use assignment if I feel like it... it seems to me that it's convenient for the human mind to model "computational objects" as little pools of shared mutable state. It's a shorthand we use also use in dealing with the real world. Even though everything is interconnected, at least at the atomic level, meaning there is no such thing as truly isolated state, we nevertheless think of the world in terms of objects. Without assignment, it seems harder to section off abstractions from each another. I guess the Haskell crowd could achieve this with monads. I'd be interested in hearing people's thoughts. Maybe this will change as I learn more about Haskell, but I still don't like it as much as I like Scheme... I don't completely know why, but I think Scheme's lack of syntax has a lot to do with it. Scheme programs look pretty and nested on the page, while Haskell looks more like a math textbook... cool in its own right, but I prefer the former as of yet... So here is my question: would it be possible to give Scheme static typing while maintaining its appeal? Has this already been done? If not, why? I haven't thought about it at length, and maybe Scheme's elegant syntax would be crushed by type annotations, but I still wonder. Why not?

Lastly, what do people think about implementations? I keep shopping around for one that I like, and I keep coming up empty. PLT falls short because it depends too much on DrScheme, and I want to use Emacs. I don't think I should have to abandon Emacs just to gain access to the stepper and interactive debugging. MzScheme's text mode debugging support seems paltry. I understand the appeal of Scheme's minimal definition, but when I'm using it for practical purposes, I don't want the API to feel tacked on. I don't want to import an object system. I want it to be there and feel like it's built-in. I don't want to load a SRFI number, I want the Scheme equivalent of saying import java.util.foo with a name that maps to functionality. I guess what I want is a Scheme that reminds me of Common Lisp while not being as ugly as Common Lisp is. I need a full-fledged toolbox, and I need it to feel seamlessly integrated. Does anyone have suggestions? If not, why doesn't such a Scheme exist?

If you read this far, thanks for your advice / comments. I have been reading and learning from this community for a long time and now I am finally a member.

I recently had a discussion about the per-abstraction complexity of interactions that must be considered before changing a system.

I claimed that the worst case OOP interactions are O(n!) where n is the number of instances in the running system.

I also claimed that worst case monadic interactions are O(n!) where n is the number of monads stacked inside the monad transformer being altered.

Those are my first thoughts on abstraction complexity, based on my experience. Are there any research papers or books on abstraction complexity?

What are your estimations of abstraction complexity, and why?

Does Abstraction add Fuzziness to software?

I observed that Asbtraction though it helps in better communication of ideas will actually add fuzziness to the program understanding when we actually have to write some code that actually works.

(The context of abstractions here is that they are in a domain , as in a financial software or some product etc.. and consider OOP and consider systems in the wild)

The reason why i feel that it adds fuzziness is that it does not immedietly allow me to write some code after understanding the abstractions.Even in a well designed system, I know what objects i should invoke, but it does not exactly tell me what should be done.It will be ok if the abstraction uses a standard design pattern, which usually is not the case.

I have found that for objects which map realworld entities, these abstractions will be easy to understand. But when these abstractions involve process information , the control flow becomes very fuzzy.I cannot figure out the exact control flow of the code from a Java source code . Some people may find this statement pretty stupid , but i think that they have trained their minds to look at things that way, but the fuzziness still remains .

For example, the processing of a transaction might involve creating lots of objects. These objects each perform a specific operation on the given transaction. This code base is was written by many teams and each team has its own way of looking at it.For example some object computes risk of that transaction, for that it needs to be instantiated with other objects whose values we should know before.For other team for the process of printing a report, a type of report might be the basic abstraction in his world.So thats additional mapping. Also once i also came across an asbtraction that was made to make it easy to test code, which is common IMHO.

Now in a large team of say 500 memebers, how do we expect people to get in proper abstractions. Refactoring the code may not be an option because there is a lot of code that runs using these abstractions. Also, the above code is a very stripped down version and for each task we need to be aware of many special cases which usually cannot be abstracted or abstraction may not make much sense or was an overkill.

The problem is only aggravated in a badly designed system as it does not follow known patterns or ways of doing things. The reason why i see bad designs at my work place is not because people are bad, but because there might be a change in the requirement which was assumed would not change, but it did change during the final stages of the testing or the system was extended beyond what it was intended to do.

Please leave your comments, opinions or flames on this issue.

First off, thanks for the most excellent blog on Programming Languages.

Can we add a section on Books (along the same level as Courses, Research Papers etc.), which would be immensely helpful. I see references and links to CTM, POPL etc. in various articles, comments, but collecting them in a single place would be good.

Best Regards,
-senthil

The server hosting LtU crashed on Thursday evening. I took this as an opportunity to migrate LtU over to a server running much newer versions of Linux, Apache, PHP, MySQL etc., which takes care of a major aspect of the long-planned upgrade to the latest version of Drupal. For the moment, we're still running the same version of Drupal, since that upgrade requires some software customizations, which are still in progress.

If you notice any problems with the site which didn't exist before, please post a message here.